package com.example.springfeature.dateconstruct;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * 定义二叉树的结构
 * Created by Administrator on 2019/3/9.
 */
public class  BinaryTree<T extends Comparable> {

    // 1.持有根节点
    private Node root;

    private volatile Integer nodeCount = 0;

    public int searchCount = 0;

    //定义二叉树中的节点结构
    class Node{
        //父节点的引用
        //左节点的引用
        //右节点的引用
        //数据
        private Node parent;
        private Node left;
        private Node right;
        private T data;

        public Node getParent() {
            return parent;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    //添加一个元素的方法
    void addOne(T data){
        //如果数为空，则该元素为树的根节点
        // 从根元素开始遍历，如果值大于根节点，则去右节点比较，否则去跟左节点比较
        // 右节点没有，则创建节点并让该节点的右节点指向新元素
        // 左节点没有，则创建节点并让该节点的左节点指向新元素
        // 如果遇到相同元素，则返回，不需要插入
        Node newNode = createNewNode(data);
        if(root == null){
            root = newNode;
            nodeCount ++;
            return;
        }
        Node thisParent = findParent(root,data);
        //如果没有找到父节点，那么直接返回，表示该元素已经存在
        if(thisParent == null){
            return;
        }
        //如果找到了，判断该节点的值与父节点值的大小，大于父节点就放在父子节点的右侧，否则左侧
        if(thisParent.getData().compareTo(data) > 0){
            thisParent.left = newNode;
            newNode.parent = thisParent;
        }else{
            thisParent.right = newNode;
            newNode.parent = thisParent;
        }
        nodeCount ++;
    }
    private Node createNewNode(T data) {
        Node node = new Node();
        node.setData(data);
        return node;
    }

    private Node findParent(Node root, T newData) {
        int compareResult =  root.getData().compareTo(newData);
        if(compareResult > 0){// 去查左子节点
            Node left = root.getLeft();
            if(left == null){//左子节点是空，那左子节点的父节点就是新插入节点的父节点
                return root;
            }else{
                return findParent(left,newData);
            }
        }else if(compareResult < 0){ // 去查右子节点
            Node right = root.getRight();
            if(right == null){// 右字节点是空，那右字节点的父节点就是新插入节点的父节点
                return root;
            }else{
                return findParent(right,newData);
            }
        }
        //比较相等的时候，表示二叉树中已经存在该元素
        return null;
    }

    private Node findNode(Node root, T newData) {
        searchCount ++;
        int compareResult = root.getData().compareTo(newData);
        if(compareResult > 0){// 去查左子节点
            Node left = root.getLeft();
            if(left == null){//没有该元素
                return null;
            }else{
                return findNode(left,newData);
            }
        }else if(compareResult < 0){ // 去查右子节点
            Node right = root.getRight();
            if(right == null){// 没有该元素
                return null;
            }else {
                return findNode(right,newData);
            }
        }else
        //比较相等的时候，表示二叉树中有该元素，那么直接返回
        return root;
    }

    public Node findData(T newData){
        return this.findNode(root,newData);
    }

    //删除一个元素的方法
    void deleteOne(T data){

    }

    //遍历所有元素的方法
    List<T> getBySort(){
        List<T> ts = new ArrayList<>();
        putToList(ts,root);
        return ts;
    }

    //将树中的节点元素全部放在数组中
    //这里使用中序遍历
    //先遍历左子树
    //在取值，然后遍历右子数
    private void putToList(List<T> ts, Node root) {
        if(root != null){
            putToList(ts,root.getLeft());
            ts.add(root.getData());
            putToList(ts,root.getRight());
        }
    }

    //使用堆栈遍历元素的方法
    //这里默认使用中序遍历
    //遇到一个节点就push到堆栈中
    //如果该节点存在左子树，那就访问左子节点
    //如果左子节点没有，判断堆栈不为空，则弹出一个节点，把节点的右子树拿来重新访问
    List<T> getBySortByStack(){
        List<T> resultList = new ArrayList<>();
        Stack<Node> ts = new Stack<>();
        Node oneNode = root;
        while(!ts.empty() || oneNode != null){
            while(oneNode != null){
                ts.push(oneNode);
                oneNode = oneNode.getLeft();
            }
            if(!ts.empty()){
                Node pop1 = ts.pop();
                resultList.add(pop1.getData());
                oneNode = pop1.getRight();
            }
        }
        return resultList;
    }

    public Integer getNodeCount() {
        return nodeCount;
    }
}
